A service function chain (“SFC”) defines a sequence of network functions (“NFs”), such as firewalls and load balancers (“LBs”), and stitches them together. The SFC has been a key enabler for network operators to offer diverse services and an important application of software defined networking (“SDN”). Recently, operators have begun to apply network functions virtualization (“NFV”) to SFC, using virtualized NFs (known as virtual network functions or “VNFs”) running on commodity servers. While NFV ameliorates some of the challenges operators face in deploying SFCs (e.g., elastic service provisioning), NFV exacerbates others. In particular, traffic traversing virtualized SFCs may suffer from reduced throughput and increased latency. Moreover, the flexibility offered by the combination of SDN and NFV might result in SFC length increasing as networks become ever more highly automated, thus making this challenge ever more relevant.